import java.util.Arrays;
import java.util.Random;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] arr = new int[]{5,4,4,4,3,2,1};
        for(int e: s.smallestK(arr, 3)) {
            System.out.print(e + " ");
        }
    }

    public int[] smallestK1(int[] arr, int k) {
        /**
         * 最小k个数*/
        // 1 预处理
        int[] retArray = new int[k];
        // -k==0需要特判，因为在quickSort函数取基准值中，无法接受k==0
        if(k == 0) {
            return retArray;
        }
        int n = arr.length;

        // 2 第k小，就是第n-k大
        quickSort(n-k, 0, arr.length-1, arr);
        for(int i = 0; i < k; i++) {
            retArray[i] = arr[i];
        }
        return retArray;
    }

    public int[] smallestK(int[] arr, int k) {
        /**
         * 最小k个数*/
        // 1 预处理
        int[] retArray = new int[k];
        // -k==0需要特判，因为在quickSort函数取基准值中，无法接受k==0
        if(k == 0) {
            return retArray;
        }
        int n = arr.length;

        // 2 第k小，就是第n-k大
        quickSort(k, 0, arr.length-1, arr);
        for(int i = 0; i < k; i++) {
            retArray[i] = arr[i];
        }
        return retArray;
    }

    public static Random random = new Random();

    public static int[] quickSort1(int k, int left, int right, int[] nums) {
        /**
         * 快速选择算法-返回数组中最小的k个数
         *  思路：
         *      1，先使用快速选择算法找第k大的数，找到时则说明k之前的所有元素均小于等于，k之后的元素均大于等于
         *      2，找到直接返回当前数组，截取前k个元素，必定是前k小的元素*/
        // 1,递归出口
        if(left == right) {
            return nums;
        }
        // 2,选择基准值（随机数）
        int key = nums[left + random.nextInt(right-left+1)];
        // 3,数组分三块
        int l = left - 1;
        int r = right + 1;
        int i = left;
        while(i < r) {
            if(nums[i] < key) {
                swap(i++, ++l, nums);
            } else if(nums[i] == key) {
                i++;
            } else {
                swap(i, --r, nums);
            }
        }
        // 4,根据k所在区间进行返回
        // -直到将k逼近到等于区间，此时由于是数组分三块，因此前k小必定在左侧（不要求有序）
        if(right - r + 1 >= k) {
            return quickSort1(k, r, right, nums);
        } else if(right - l >= k) {
            return nums;
        } else {
            return quickSort1(k - right + l, left, l, nums);
        }
    }

    public static int[] quickSort(int k, int left, int right, int[] nums) {
        /**
         * 快速排序算法：
         *  找到第k小的元素*/
        // 1,递归出口
        if(left == right) {
            return nums;
        }
        // 2,选择基准值（随机数）
        int key = nums[left + random.nextInt(right-left+1)];
        // 3,数组分三块
        int l = left - 1;
        int r = right + 1;
        int i = left;
        while(i < r) {
            if(nums[i] < key) {
                swap(i++, ++l, nums);
            } else if(nums[i] == key) {
                i++;
            } else {
                swap(i, --r, nums);
            }
        }
        // 4,根据k所在区间进行返回
        if(l-left+1 >= k) {
            // -在小于部分
            return quickSort(k, left, l, nums);
        } else if(r-left >= k) {
            return nums;
        } else {
            return quickSort(k-r+left, r, right, nums);
        }
    }

    public static void swap(int a, int b, int[] nums) {
        /**
         * 在数组中交换两个元素的位置*/
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}
